package com.javabasic.algorithm.sword_of_offer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/1/24 10:48 下午
 */
public class 剑指_Offer_34_二叉树中和为某一值的路径 {

    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if (root == null) {
            return result;
        }
        String numStr = String.valueOf(root.val);
        dfs(root,target-root.val,numStr);
        return result;
    }

    /**
     * 暴力回溯
     * @param root
     * @param target
     * @param numStr
     */
    private void dfs(TreeNode root, int target, String numStr) {
        if (root.left == null && root.right == null) {
            if (0 == target) {
                String[] nums = numStr.split(",");
                List<Integer> numList = new ArrayList<>();
                for (String num : nums) {
                    numList.add(Integer.valueOf(num));
                }
                result.add(numList);
            }
            return;
        }
        if (root.left != null) {
            dfs(root.left,target-root.left.val, numStr + "," + root.left.val);
        }
        if (root.right != null) {
            dfs(root.right,target-root.right.val, numStr + "," + root.right.val);
        }
    }
}
